package com.cuz.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Q15ThreeNumSum {

    public static void main(String[] args) {
        int[] ints = {1,2,-2,-1};
        System.out.println(threeSum1(ints));
    }

    public static List<List<Integer>> threeSum1(int[] nums) {
        if (nums == null || nums.length <= 2) {
            return Collections.emptyList();
        }
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        //数组第一个数大于0 那么返回空白 比如 1，2，3，5 不可能等于0
        if (nums[0] > 0) {
            return res;
        }
        //枚举第一个数
        for (int start = 0; start < nums.length - 2; start++) {
            //第一个数大于0 那么直接break 后面不存在三数之和=0
            if (nums[start] > 0) {
                break;
            }
            //去除重复
            //-1 -1 -1，0，1 找到第一个 -1 0 1 后面-1都 跳过
            if (start > 0 && nums[start] == nums[start - 1]) {
                continue;
            }
            //第二个数
            int mid = start + 1;
            //第三个数
            int end = nums.length - 1;
            //第二个数下标不可以大于第三个数
            while (mid < end) {
                //目前三数和
                int tempSum = nums[start] + nums[end] + nums[mid];
                //是我们的目标
                if (tempSum == 0) {
                    res.add(Arrays.asList(nums[start], nums[mid], nums[end]));
                    //只要找到了 必定mid++;   end--; 因为 start end、不动mid++ 必定只能大于0
                    //start mid 不动 end--只能小于0
                    //- 2  -1  0  1  2   找到-2 0 2之后二者一起毕竟才能找到-1 0 1的组合
                    mid++;
                    end--;
                    //比如 -2  -2  0      2  避免两个 -2 0 2 的组合
                    while (mid < end && nums[mid] == nums[mid - 1]) {
                        mid++;
                    }
                    //比如 -2 0  2  2 避免两个 -2 0 2 的组合
                    while (mid < end && nums[end] == nums[end + 1]) {
                        end--;
                    }
                } else if (tempSum > 0) {
                    end--;
                } else {
                    mid++;
                }

            }
        }
        return res;
    }
}
